package com.poxz.algorithm.template;

import java.util.*;

/**
 * 图论算法
 *
 * @author poxz
 */
public class GraphAlgorithms {

    // ==================== 并查集 ====================

    /**
     * 并查集（路径压缩 + 按秩合并）
     * 时间复杂度: O(α(n))，α为阿克曼函数的反函数，几乎为常数
     */
    static class UnionFind {
        int[] parent;  // 父节点
        int[] rank;    // 秩（树的高度）
        int count;     // 连通分量个数

        UnionFind(int n) {
            parent = new int[n];
            rank = new int[n];
            count = n;
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                rank[i] = 1;
            }
        }

        // 查找根节点（路径压缩）
        int find(int x) {
            if (parent[x] != x) {
                parent[x] = find(parent[x]);  // 路径压缩
            }
            return parent[x];
        }

        // 合并两个集合（按秩合并）
        boolean union(int x, int y) {
            int rootX = find(x);
            int rootY = find(y);

            if (rootX == rootY) return false;

            // 按秩合并
            if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY;
            } else if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
            count--;
            return true;
        }

        // 判断是否连通
        boolean isConnected(int x, int y) {
            return find(x) == find(y);
        }

        // 获取连通分量个数
        int getCount() {
            return count;
        }
    }

    // ==================== 最短路算法 ====================

    /**
     * Dijkstra算法 - 单源最短路（正权边）
     * 时间复杂度: O((V+E)logV)
     *
     * @param graph 邻接表 graph[u] = [(v, w), ...] 表示u->v权重为w
     * @param start 起点
     * @param n     节点数
     * @return 从start到各节点的最短距离
     */
    static long[] dijkstra(List<int[]>[] graph, int start, int n) {
        long[] dist = new long[n];
        Arrays.fill(dist, Long.MAX_VALUE);
        dist[start] = 0;

        // 优先队列：[距离, 节点]
        PriorityQueue<long[]> pq = new PriorityQueue<>((a, b) -> Long.compare(a[0], b[0]));
        pq.offer(new long[]{0, start});

        while (!pq.isEmpty()) {
            long[] curr = pq.poll();
            long d = curr[0];
            int u = (int) curr[1];

            if (d > dist[u]) continue;  // 已经找到更短路径

            for (int[] edge : graph[u]) {
                int v = edge[0];
                int w = edge[1];

                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    pq.offer(new long[]{dist[v], v});
                }
            }
        }
        return dist;
    }

    /**
     * Bellman-Ford算法 - 单源最短路（可处理负权边）
     * 时间复杂度: O(VE)
     *
     * @param edges 边集 [u, v, w] 表示u->v权重为w
     * @param start 起点
     * @param n     节点数
     * @return 从start到各节点的最短距离，null表示存在负环
     */
    static long[] bellmanFord(int[][] edges, int start, int n) {
        long[] dist = new long[n];
        Arrays.fill(dist, Long.MAX_VALUE);
        dist[start] = 0;

        // 松弛n-1次
        for (int i = 0; i < n - 1; i++) {
            for (int[] edge : edges) {
                int u = edge[0], v = edge[1], w = edge[2];
                if (dist[u] != Long.MAX_VALUE && dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                }
            }
        }

        // 检测负环
        for (int[] edge : edges) {
            int u = edge[0], v = edge[1], w = edge[2];
            if (dist[u] != Long.MAX_VALUE && dist[u] + w < dist[v]) {
                return null;  // 存在负环
            }
        }
        return dist;
    }

    /**
     * Floyd算法 - 多源最短路
     * 时间复杂度: O(V^3)
     *
     * @param graph 邻接矩阵，graph[i][j]表示i->j的权重
     * @return 任意两点间的最短距离
     */
    static long[][] floyd(long[][] graph) {
        int n = graph.length;
        long[][] dist = new long[n][n];

        // 初始化
        for (int i = 0; i < n; i++) {
            dist[i] = graph[i].clone();
        }

        // k为中间节点
        for (int k = 0; k < n; k++) {
            for (int i = 0; i < n; i++) {
                for (int j = 0; j < n; j++) {
                    if (dist[i][k] != Long.MAX_VALUE && dist[k][j] != Long.MAX_VALUE) {
                        dist[i][j] = Math.min(dist[i][j], dist[i][k] + dist[k][j]);
                    }
                }
            }
        }
        return dist;
    }

    /**
     * SPFA算法 - 单源最短路（队列优化的Bellman-Ford）
     * 平均时间复杂度: O(E)，最坏O(VE)
     *
     * @param graph 邻接表
     * @param start 起点
     * @param n     节点数
     * @return 从start到各节点的最短距离，null表示存在负环
     */
    static long[] spfa(List<int[]>[] graph, int start, int n) {
        long[] dist = new long[n];
        int[] cnt = new int[n];  // 记录入队次数，用于检测负环
        boolean[] inQueue = new boolean[n];

        Arrays.fill(dist, Long.MAX_VALUE);
        dist[start] = 0;

        Deque<Integer> queue = new ArrayDeque<>();
        queue.offer(start);
        inQueue[start] = true;

        while (!queue.isEmpty()) {
            int u = queue.poll();
            inQueue[u] = false;

            for (int[] edge : graph[u]) {
                int v = edge[0];
                int w = edge[1];

                if (dist[u] + w < dist[v]) {
                    dist[v] = dist[u] + w;
                    cnt[v] = cnt[u] + 1;

                    if (cnt[v] >= n) return null;  // 存在负环

                    if (!inQueue[v]) {
                        queue.offer(v);
                        inQueue[v] = true;
                    }
                }
            }
        }
        return dist;
    }

    // ==================== 最小生成树 ====================

    /**
     * Kruskal算法 - 最小生成树
     * 时间复杂度: O(ElogE)
     *
     * @param edges 边集 [u, v, w] 表示u-v权重为w
     * @param n     节点数
     * @return [最小权重和, 选中的边]
     */
    static Object[] kruskal(int[][] edges, int n) {
        // 按权重排序
        Arrays.sort(edges, (a, b) -> a[2] - b[2]);

        UnionFind uf = new UnionFind(n);
        List<int[]> mst = new ArrayList<>();
        long totalWeight = 0;

        for (int[] edge : edges) {
            int u = edge[0], v = edge[1], w = edge[2];

            if (uf.union(u, v)) {
                mst.add(edge);
                totalWeight += w;

                if (mst.size() == n - 1) break;  // 已构成树
            }
        }

        return new Object[]{totalWeight, mst};
    }

    /**
     * Prim算法 - 最小生成树
     * 时间复杂度: O((V+E)logV)
     *
     * @param graph 邻接表
     * @param n     节点数
     * @return 最小权重和
     */
    static long prim(List<int[]>[] graph, int n) {
        boolean[] visited = new boolean[n];
        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[1] - b[1]);  // [节点, 权重]

        long totalWeight = 0;
        int edgeCount = 0;

        // 从节点0开始
        pq.offer(new int[]{0, 0});

        while (!pq.isEmpty() && edgeCount < n) {
            int[] curr = pq.poll();
            int u = curr[0], w = curr[1];

            if (visited[u]) continue;

            visited[u] = true;
            totalWeight += w;
            edgeCount++;

            for (int[] edge : graph[u]) {
                int v = edge[0], weight = edge[1];
                if (!visited[v]) {
                    pq.offer(new int[]{v, weight});
                }
            }
        }

        return edgeCount == n ? totalWeight : -1;  // -1表示不连通
    }

    // ==================== 拓扑排序 ====================

    /**
     * 拓扑排序 - Kahn算法（BFS）
     * 时间复杂度: O(V + E)
     *
     * @param graph   邻接表
     * @param inDegree 入度数组
     * @param n       节点数
     * @return 拓扑排序序列，null表示存在环
     */
    static List<Integer> topologicalSort(List<Integer>[] graph, int[] inDegree, int n) {
        List<Integer> result = new ArrayList<>();
        Deque<Integer> queue = new ArrayDeque<>();

        // 将入度为0的节点入队
        for (int i = 0; i < n; i++) {
            if (inDegree[i] == 0) {
                queue.offer(i);
            }
        }

        while (!queue.isEmpty()) {
            int u = queue.poll();
            result.add(u);

            for (int v : graph[u]) {
                inDegree[v]--;
                if (inDegree[v] == 0) {
                    queue.offer(v);
                }
            }
        }

        return result.size() == n ? result : null;  // 未能排序所有节点说明有环
    }

    /**
     * 拓扑排序 - DFS版本
     * 时间复杂度: O(V + E)
     *
     * @param graph 邻接表
     * @param n     节点数
     * @return 拓扑排序序列，null表示存在环
     */
    static List<Integer> topologicalSortDFS(List<Integer>[] graph, int n) {
        int[] state = new int[n];  // 0:未访问 1:访问中 2:已完成
        Deque<Integer> stack = new ArrayDeque<>();

        for (int i = 0; i < n; i++) {
            if (state[i] == 0) {
                if (!dfsTopoSort(graph, i, state, stack)) {
                    return null;  // 存在环
                }
            }
        }

        List<Integer> result = new ArrayList<>();
        while (!stack.isEmpty()) {
            result.add(stack.pop());
        }
        return result;
    }

    private static boolean dfsTopoSort(List<Integer>[] graph, int u, int[] state, Deque<Integer> stack) {
        state[u] = 1;  // 标记为访问中

        for (int v : graph[u]) {
            if (state[v] == 1) return false;  // 发现环
            if (state[v] == 0) {
                if (!dfsTopoSort(graph, v, state, stack)) {
                    return false;
                }
            }
        }

        state[u] = 2;  // 标记为已完成
        stack.push(u);
        return true;
    }

    // ==================== 强连通分量 ====================

    /**
     * Tarjan算法 - 强连通分量
     * 时间复杂度: O(V + E)
     *
     * @param graph 邻接表
     * @param n     节点数
     * @return 每个强连通分量的节点列表
     */
    static List<List<Integer>> tarjanSCC(List<Integer>[] graph, int n) {
        int[] dfn = new int[n];      // 时间戳
        int[] low = new int[n];      // 能回溯到的最早时间戳
        boolean[] inStack = new boolean[n];
        Deque<Integer> stack = new ArrayDeque<>();
        List<List<Integer>> sccs = new ArrayList<>();

        int[] timestamp = {0};  // 使用数组包装以在lambda中修改

        for (int i = 0; i < n; i++) {
            if (dfn[i] == 0) {
                tarjanDFS(graph, i, dfn, low, inStack, stack, sccs, timestamp);
            }
        }
        return sccs;
    }

    private static void tarjanDFS(List<Integer>[] graph, int u, int[] dfn, int[] low,
                                   boolean[] inStack, Deque<Integer> stack,
                                   List<List<Integer>> sccs, int[] timestamp) {
        dfn[u] = low[u] = ++timestamp[0];
        stack.push(u);
        inStack[u] = true;

        for (int v : graph[u]) {
            if (dfn[v] == 0) {
                tarjanDFS(graph, v, dfn, low, inStack, stack, sccs, timestamp);
                low[u] = Math.min(low[u], low[v]);
            } else if (inStack[v]) {
                low[u] = Math.min(low[u], dfn[v]);
            }
        }

        // 找到强连通分量的根
        if (dfn[u] == low[u]) {
            List<Integer> scc = new ArrayList<>();
            int v;
            do {
                v = stack.pop();
                inStack[v] = false;
                scc.add(v);
            } while (v != u);
            sccs.add(scc);
        }
    }

    /**
     * 功能测试
     *
     * @param args 命令行参数
     */
    @SuppressWarnings("unchecked")
    public static void main(String[] args) {
        System.out.println("=== 图论算法示例 ===\n");

        // 并查集测试
        System.out.println("--- 并查集 ---");
        UnionFind uf = new UnionFind(5);
        uf.union(0, 1);
        uf.union(2, 3);
        System.out.println("0和1连通? " + uf.isConnected(0, 1));
        System.out.println("0和2连通? " + uf.isConnected(0, 2));
        System.out.println("连通分量个数: " + uf.getCount());
        System.out.println();

        // Dijkstra测试
        System.out.println("--- Dijkstra最短路 ---");
        int n = 5;
        List<int[]>[] graph = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
        graph[0].add(new int[]{1, 10});
        graph[0].add(new int[]{4, 5});
        graph[1].add(new int[]{2, 1});
        graph[1].add(new int[]{4, 2});
        graph[2].add(new int[]{3, 4});
        graph[3].add(new int[]{0, 7});
        graph[3].add(new int[]{2, 6});
        graph[4].add(new int[]{1, 3});
        graph[4].add(new int[]{2, 9});
        graph[4].add(new int[]{3, 2});

        long[] dist = dijkstra(graph, 0, n);
        System.out.println("从节点0到各节点的最短距离: " + Arrays.toString(dist));
        System.out.println();

        // Kruskal最小生成树测试
        System.out.println("--- Kruskal最小生成树 ---");
        int[][] edges = {
                {0, 1, 10}, {0, 4, 5}, {1, 2, 1}, {1, 4, 2},
                {2, 3, 4}, {3, 0, 7}, {3, 2, 6}, {4, 1, 3},
                {4, 2, 9}, {4, 3, 2}
        };
        Object[] mstResult = kruskal(edges, 5);
        System.out.println("最小生成树权重和: " + mstResult[0]);
        System.out.println("选中的边:");
        for (int[] edge : (List<int[]>) mstResult[1]) {
            System.out.println("  " + edge[0] + " - " + edge[1] + " : " + edge[2]);
        }
        System.out.println();

        // 拓扑排序测试
        System.out.println("--- 拓扑排序 ---");
        int n2 = 6;
        List<Integer>[] dag = new ArrayList[n2];
        for (int i = 0; i < n2; i++) {
            dag[i] = new ArrayList<>();
        }
        dag[5].add(2);
        dag[5].add(0);
        dag[4].add(0);
        dag[4].add(1);
        dag[2].add(3);
        dag[3].add(1);

        int[] inDegree = new int[n2];
        for (int i = 0; i < n2; i++) {
            for (int j : dag[i]) {
                inDegree[j]++;
            }
        }

        List<Integer> topoOrder = topologicalSort(dag, inDegree, n2);
        System.out.println("拓扑排序结果: " + topoOrder);
    }
}

